We describe a polynomial time algorithm that takes as input a polygon with axis-parallel sides but irrational vertex coordinates, and outputs a set of as few rectangles as possible into which it can be dissected by axis-parallel cuts and translations. The number of rectangles is the rank of the Dehn invariant of the polygon. The same method can also be used to dissect an axis-parallel polygon into a simple polygon with the minimum possible number of edges. When rotations or reflections are allowed, we can approximate the minimum number of rectangles to within a factor of two.
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
more » « less
Abstract -
Abstract We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter $$\lambda $$ λ , the number of different minimum spanning trees obtained as the parameter varies can be $$\Omega (m\log n)$$ Ω ( m log n ) .more » « lessFree, publicly-accessible full text available June 1, 2024
-
Free, publicly-accessible full text available June 1, 2024
Full Text Available